package com.wlj.utils.suanfa;

import java.util.ArrayList;

public class SparseGraph {

    private int n,m; //顶点，边
    private ArrayList<ArrayList<Edge>> g=new ArrayList<>();  //邻接表


    public SparseGraph(int n, int[][] edges) {
        this.n = n;
        this.m=edges.length;
        for(int i=0;i<n;i++){
            ArrayList<Edge> arr=new ArrayList<Edge>();
            g.add(arr);
        }
    }

    public int V(){return n;}
    public int E(){return m;}

    //获取n点所有邻边
    public ArrayList<Edge> getSideEdges(int n){
        return g.get(n-1);
    }

    public void addEdge(int v,int w,int weight){
        assert(v>=0&&v<n);
        assert(w>=0&&w<n);
        if(hasEdge(v,w))     //防止重复添加边，排除平行边
            return;
        if(v!=w){
            ArrayList<Edge> arr=g.get(v-1);
            ArrayList<Edge> srr=g.get(w-1);
            arr.add(new Edge(v,w,weight));
            srr.add(new Edge(v,w,weight));
            m++;
        }
    }
    public boolean hasEdge(int v,int w){
        assert(v>=0&&v<n);
        assert(w>=0&&w<n);
        ArrayList<Edge> arr=g.get(v-1);
        for(int i=0;i<arr.size();i++){
            if(arr.get(i).other(v)==w)
                return true;
        }
        return false;
    }
}
